Data is often archived or transmitted in a compressed format to minimize system resources required for storage or handling of the data. Compression encoding may be lossless or lossy. Lossless compression is utilized in applications where original data must be recovered. Where it is sufficient for a decoding process to recover an approximation of the original data, lossy compression codecs are often utilized for the sake of greater compression rates.
Run length encoding (RLE) is a technique for removing data redundancy/repetition and is employed by many standardized lossless and lossy compression algorithms now ubiquitous in the digital world. RLE specifies a length of a repetitive “run” and the run-ending “level.” A form of RLE is often used for example in fax transmissions and for binary bitmap images. RLE may also be utilized within a lossless compression stage of a lossy compression pipeline. In lossy compression, a raw data stream (e.g., pictures and sound in an A/V codec compliant with MPEG-4, H.264 AVC, etc.) may be sampled and segmented (e.g., into macroblocks), transformed (e.g., through discrete cosine transform), and quantized. The resulting coefficients may then be entropy encoded. The entropy encoding stage may employ a lossless compression algorithm to remove as much redundancy as possible from the input data (e.g., DCT block). Many standardized forms of entropy encoding permit the use of RLE because after quantization a significant number of the higher order AC coefficients of a DCT block may be zeros. A run of zeros within sparse DCT data can then be represented by a “run-level” pair specifying the length of a zero run and the run-ending non-zero level (e.g. non-zero DCT coefficient). Run-level pairs output by the RLE encoder may then be statistically coded (e.g., via a Huffman table) where the length of the code symbol assigned is a function of the frequency a run-level pair appears. If this is the final operation in the encoding process, the result is the compressed data stream.
There are many instances where it is useful to embed supplemental data into a compressed data stream. Depending on the application (e.g., data security, digital rights management (DRM), user experience enhancement, etc.), such supplemental data may be overtly or covertly embedded into a compressed data stream. Covert data embedding, often referred to as “data hiding,” includes watermarking and steganography. Techniques and systems to embed supplemental data into a compressed data stream, particularly those compatible with existing lossy and lossless compression codecs, are therefore advantageous.